package personal.leil.learning.exercises;

import java.util.HashMap;

/**
 * 复制含有随机指针节点的链表
 * <p>
 * 一种特殊的单链表节点类描述如下 <br/>
 * <pre>
 * class Node {
 *  int value;
 *  Node next;
 *  Node rand;
 *  Node(int val) {
 *      value = val;
 *  }
 * </pre>
 * rand指针是单链表节点结构中新增的指针，
 * rand可能指向链表中的任意一个节点，
 * 也可能指向null。<br/>
 * 给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。<br/>
 * [要求]时间复杂度0(N)，额外空间复杂度0(1)
 * </p>
 */
public class Question4 {

    static class Node {
        Node next;
        Node rand;
        int value;

        Node(int val) {
            this.value = val;
        }

        Node copy() {
            return new Node(this.value);
        }
    }


    public static Node buildLinkedList() {
        Node head = new Node(20);
        Node node1 = new Node(22);
        Node node2 = new Node(11);
        Node node3 = new Node(66);
        Node node4 = new Node(88);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        head.rand = node4;
        node1.rand = node4;
        node3.rand = head;
        node4.rand = node3;
        return head;
    }

    public static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        sb.append(head.value);
        System.out.println("[" + head + "]" + head.value + "::rand::" + (head.rand == null ? "Null" : head.rand.value));
        Node current = head;
        while (current.next != null) {
            Node next = current.next;
            sb.append("=>");
            sb.append(next.value);
            System.out.println("[" + current.next + "]" + current.next.value + "::rand::" + (current.next.rand == null ? "Null" : current.next.rand.value));
            current = next;
        }
        System.out.println(sb);
    }


    /**
     * 不考虑额外空间复杂度
     *
     * @param head head for linked list
     * @return linked list for copy
     */
    public static Node process1(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node current = head;
        while (current != null) {
            Node copy = current.copy();
            map.put(current, copy);
            current = current.next;
        }

        current = head;
        while (current != null) {
            Node copy = map.get(current);
            copy.next = map.get(current.next);
            if (current.rand != null) {
                copy.rand = map.get(current.rand);
            }
            current = current.next;
        }

        return map.get(head);
    }

    /**
     * 额外空间复杂度为O(1)
     * <p>
     * 1、将原链表每个节点copy后连接到原节点后 <br/>
     * 2、处理copy节点的rand <br/>
     * 3、拆分原链表和copy链表 <br/>
     * </p>
     *
     * @param head head for linked list
     * @return linked list for copy
     */
    public static Node process2(Node head) {
        Node current = head;
        while (current != null) {
            Node next = current.next;
            Node copy = current.copy();
            current.next = copy;
            copy.next = next;
            current = next;
        }
//        printLinkedList(head);
        /*
         * 一直要处理到原链表到最后一个节点，才能将所有的rand情况都处理完成
         */
        current = head;
        while (current != null) {
            Node next = current.next.next;
            // 先处理rand
            Node copy = current.next;
            copy.rand = current.rand == null ? null : current.rand.next;
            current = next;
        }
        /*
         * 将链表分拆
         * 由于最后一对节点只需要向前连接就可以，所以只要处理到原链表倒数第二个节点就可以完成拆分
         */
        current = head;
        Node copyHead = current.next;
        while (current.next.next != null) {
            Node next = current.next.next;
            Node copy = current.next;
            copy.next = next.next;
            current.next = next;
            current = next;
        }
        return copyHead;
    }

    /********************* For Test *************************/

    public static void main(String[] args) {
        Node head = buildLinkedList();
        printLinkedList(head);
        System.out.println("linked list for copy:");
        Node copy = process2(head);
        printLinkedList(copy);
    }


}
